1. Field of the Invention
The present invention generally relates to certificates for digital signature verification and, more particularly, to a method for undeniably certifying a public signing key for a recipient to verify digital signatures which precludes third parties from verifying the signatures yet does not require the original signer's cooperation with the recipient on each signature except for an initial verification.
2. Description of the Related Art
With the proliferation of electronic mail (e-mail), electronic contracts, electronic funds transfer, and the increasing reliance on on-line communication by the business community at large, the ability to authenticate documents and verify electronic or digital signatures is crucial.
Techniques have been developed for electronic authentication, for example, by using public key (PK) signatures which comprise a pair of keys associated with a particular signer. Namely, a private signing key and a public verification key. The message to be signed is represented as a number as is the signature itself. A signing algorithm is used to compute the signature using the user's private key. The signature can thereafter be verified as being attached to a particular message using the corresponding public verification key. Since the signer's private key is necessary to compute the digital signature, the forgery problem is thought to be eliminated. The ability for any third party using the corresponding public key to verify the validity of a signature is usually seen as the basis for the "non-repudiation" aspect of digital signatures, and their main source of attractiveness. However, this universal verifiability (or self-authenticating) property of digital signatures is not always a desirable property.
Such is the case of a signature binding parties to a confidential agreement, or of a signature on documents carrying private or personal information. In these cases limiting the ability of third parties to verify the validity of a signature is an important goal. However, if third party verification is limited to such an extent that it cannot be verified by, say, a court in case of a dispute then the value of digital signatures is seriously questioned. Thus, the question is raised of how to generate signatures which limit the verification capabilities yet without compromising the central property of non-repudiation.
To this end, the concept of "undeniable signatures" has been developed. The first example of undeniable signatures appeared in a paper by Michael Rabin, Digitized Signatures, Foundations of Secure Computation, Academic Press, 1978, herein incorporated by reference. When the authenticity of a message and its "undeniable signature" are called into question, the alleged signer's cooperation is required to verify the signature. That is, the alleged signer must be called upon to engage in a "confirmation protocol". On the other hand, the signer can prove that a digital signature is a forgery by engaging in a "denial protocol". This method requires that if on a specific message and signature the confirmation protocol reveals that the signature is a valid signature then using the same input to the denial protocol would not output that it is a forgery.
The protection of signatures from universal verifiability with the undeniable signature method is not only justified by confidentiality and privacy concerns but it also opens a wide range of applications where verifying a signature is a valuable operation in itself. For example, undeniable signatures are useful to software companies or other electronic publishers that use signature confirmation as a way to provide proof of authenticity on their products only to paying customers.
There are three main components to undeniable signature schemes. The signature generation algorithm (including the details of private and public information), the confirmation protocol, and the denial protocol. Signature generation is much like a regular signature generation, namely, an operation is performed by the signer on the message which results in a string that is provided to the requester of the signature. The confirmation protocol is usually modeled after an interactive proof where the signer acts as the prover and the holder of the signature as the verifier. The input to the protocol is the message and its alleged signature (as well as the public key information associated with the signer).
The validity of an undeniable signature can be gathered by anyone with whom the signer is willing to cooperate by issuing a challenge to the signer and testing the signer's response. If the results of the confirmation protocol is positive, then there is a high probability that the signature is valid. If on the other hand, the results of the confirmation protocol is negative then there is a high probability that the signature is a forgery. For more information on undeniable signatures, the reader is invited to review U.S. Pat. No. 4,947,430 to Chaum, herein incorporated by reference.
Similarly, U.S. Pat. No. 5,493,614 to Chaum, herein incorporated by reference, discloses undeniable signature scheme called private signature and proof system. In this system, a signature or proof can be sent as a single message. This solution requires prior knowledge of the intended recipient for a signatures proof.
A drawback to undeniable signature schemes is that they require the cooperation of the signer to prove a signature. There is a real need in the art of undeniable signatures to limit the amount of interaction and computational effort required to verify signatures. Namely, it is desirable to have a method by which a recipient can verify the validity of several signatures non-interactively and efficiently, after a minimal interaction with the signer.